The approaches described in this section could be pursued, but are not necessarily approaches that previously have been conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
Computers and other devices equipped with network interface hardware may be connected together to form a network that allows the devices to communicate data with each other. An example of such a network is a local area network (LAN). A LAN may be composed of several different LAN segments. All devices connected to a given LAN segment receive all of the data communicated through the given LAN segment.
For example, a LAN segment's data traffic may be transmitted over a single cable that functions as a bus. In such a configuration, all devices connected to the single cable receive all of the data communicated over the single cable, although individual devices may implement filters to selectively ignore some of the received data.
For another example, a LAN segment's data traffic may be transmitted over multiple cables that are interconnected through one or more network hubs. When a network hub receives data through a cable that is connected to one of the network hub's network interfaces, the network hub repeats the data through all of the other cables that are connected to the network hub's other network interfaces. Every device that is connected to one of the other cables receives the data. Like a single cable, the network hub operates at the physical layer of the Open Systems Interconnect (OSI) model. Regardless of whether a particular LAN segment's data traffic is transmitted over a single cable, a set of cables interconnected through one or more network hubs, or through wireless media, every device that is “on” the particular LAN segment receives all of the data that is communicated over the LAN segment.
Two or more LAN segments may be interconnected through a network bridge. Unlike a network hub, which operates at the physical layer of the OSI model, a network bridge operates at the data link layer of the OSI model. A network hub merely repeats received data through all of the network hub's network interfaces other than the network interface on which the data was received. In contrast, a network bridge, in response to receiving data through a cable that is connected to one of the network bridge's network interfaces, selects zero or more of the network bridge's network interfaces through which the data should be transmitted. Each of the network bridge's network interfaces may be connected to a different LAN segment.
For each network frame that the network bridge receives, the network bridge makes this selection based on data link layer address information, such as Media Access Control (MAC) address information, that is indicated within the network frame. For example, based on a destination MAC address indicated in a given network frame, a network bridge may determine that the network frame should be transmitted through a particular one of several of the network bridge's network interfaces in order to send the network frame over a LAN segment that forms part of the route to the network frame's ultimate destination. Another network bridge that is connected to the same LAN segment may receive the network frame and select yet another LAN segment over which the network frame should be transmitted. Thus, a network bridge may interconnect multiple LAN segments, and a LAN segment may interconnect multiple network bridges.
The data link layer topology, or “Layer 2” topology, of a LAN indicates how a LAN's bridges are connected to each other. In other words, a LAN's data link layer topology indicates, for each LAN segment in a LAN, which network bridges are connected to the LAN segment. Network hubs, which may comprise part of a LAN segment, do not need to be indicated distinctly from a LAN segment in a data link layer topology, because, as described above, network hubs operate at the physical layer rather than the data link layer. The data link layer topology of a LAN is a valuable aid in analyzing and configuring the LAN.
While the data link layer topology of a small LAN with few network bridges and LAN segments may be determined manually with reasonable effort, manually determining the data link layer topology of a large LAN with many network bridges and LAN segments can be extremely difficult. The dynamic nature of many LANs compounds the complexity of such a determination. Over time, the data link layer topology of a LAN can change, due to the addition, removal, reconfiguration, or failure of network devices and network media.
To determine the data link layer topology of large, dynamic LANs, several approaches for automatically calculating a LAN's data link layer topology have been devised. Cisco Systems, Inc. developed the Cisco Discovery Protocol (CDP). A particular network bridge that is configured to use CDP can automatically discover other network bridges that are connected to the same LAN segment as the particular network bridge, provided that the other network bridges are also configured to use CDP. Using the information discovered through CDP, the data link layer topology of a LAN may be determined if all of the LAN's network bridges are configured to use CDP. This CDP-based approach was implemented in Cisco Systems, Inc.'s CiscoWorks 2000 product.
While the CDP-based approach is effective in determining the data link layer topology of a LAN in which there are no network bridges that are unable to use CDP, the CDP-based approach may fail to determine the complete data link layer topology of a LAN in which there are one or more network bridges that are not CDP-enabled. Unfortunately, many existing LANs contain network bridges that are not CDP-enabled.
Another approach to automatically determining the data link layer topology of large, dynamic LANs may be called the MAC-based approach. The MAC-based approach takes advantage of MAC address information contained in Management Information Bases (MIBs) to determine a LAN's data link layer topology. MIBs are described in the Internet Engineering Task Force (IETF) Request For Comments (RFC) 1156 and in IETF RFC 1213. A specific Bridge MIB, described in IETF RFC 1493, specifies an object named “dot1dTpFdbTable”; “dot1d” refers to the Institute of Electrical and Electronics Engineers (IEEE) 802.1d standard.
Each network bridge maintains a dot1dTpFdbTable object. The dot1dTpFdbTable object contains information about unicast entries for which the network bridge has forwarding or filtering information. The network bridge uses such entries to determine how to propagate a received network frame. Each dot1dTpFdbTable object is an collection of one or more “dot1dTpFdbEntry” objects.
Each dot1dTpFdbEntry object contains a “dot1dTpFdbAddress” object and an associated “dot1dTpFdbPort” object. The value of a dot1dTpFdbAddress object is a MAC address, and the value of a dot1dTpFdbPort object identifies one of the network bridge's network interfaces. After receiving a network frame, a network bridge transmits the network frame through the network interface associated with the network frame's destination MAC address.
In order to determine whether a first network bridge's network interface and a second network bridge's network interface are connected to the same LAN segment, the MAC-based approach obtains all of the values of the dot1dTpFdbAddress and dot1dTpFdbPort objects maintained by the first network bridge, and all of the values of the dot1dTpFdbAddress and dot1dTpFdbPort objects maintained by the second network bridge. Based on these values, the MAC-based approach determines whether any of the obtained MAC addresses are associated with both the first network bridge's network interface and the second network bridge's network interface. If at least one of the MAC addresses is associated with both of the network interfaces, then the network interfaces are not connected to the same LAN segment. If none of the MAC addresses is associated with both of the network interfaces, then the network interfaces are connected to the same LAN segment.
Therefore, in order to determine the data link layer connectivity between just two network bridges, the MAC-based approach requires values of all of the dot1dTpFdbAddress and dot1dTpFdbPort objects maintained by the first network bridge, and values of all of the dot1dTpFdbAddress and dot1dTpFdbPort objects maintained by the second network bridge. In LANs that contain many network devices, each network bridge maintains many of such objects. Obtaining many MAC addresses and associated network interface identities can take a substantial amount of time and use a substantial amount of bandwidth. From a practical standpoint, the MAC-based approach lacks scalability.
Based on the foregoing, there is a clear need for a scalable method of automatically determining the data link layer topology of a LAN that contains one or more network bridges that are not CDP-enabled.